package 力扣日常刷题.木22一月.第01天0108;

/**
 * @author 帅小伙
 * @date 2022/1/8
 * @description
 * https://leetcode-cn.com/problems/number-of-provinces/
 */
public class Demo02并查集省份相连 {


    int[] p;
    int res;
    public int findCircleNum(int[][] isConnected) {
       res = isConnected.length;
       p = new int[isConnected.length];

        for (int i = 0; i < p.length; i++) {
            p[i] = i;
        }

        for (int i = 0; i < isConnected.length; i++) {
            for (int j = 0; j < isConnected.length; j++) {
                if(isConnected[i][j] == 1){
                    union(i,j);
                }
            }
        }

        return res;
    }

    public int find(int x){
        if(x!=p[x]) p[x] = find(p[x]);
        return p[x];
    }

    public void union(int x,int y){
        int i = find(x);
        int j = find(y);

        if(i!=j){
            res--;
            p[i] = p[j];
        }
    }
}
